package com.leetcode.August;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Description: 39. 组合总和
 * @Author: Mr.Fxy
 * @CreateTime: 2024-08-12 11:10
 */
public class LC39组合总和 {
    //    public List<List<Integer>> combinationSum(int[] candidates, int target) {
//        List<List<Integer>> res = new ArrayList<>();
//        List<Integer> subList = new ArrayList<>();
//        dfs(res, subList, candidates, target, 0);
//        return res;
//    }
//    private void dfs(List<List<Integer>> res, List<Integer> subList, int[] candidates, int target, int index) {
//
//        if (index == candidates.length) {
//            return;
//
//        }
//        if (target == 0) {
//            res.add(new ArrayList<>(subList));
//            return;
//        }
//        dfs(res, subList, candidates, target, index + 1);
//        if (target - candidates[index] >= 0) {
//            subList.add(candidates[index]);
//            dfs(res, subList, candidates, target - candidates[index], index);
//            subList.remove(subList.size() - 1);
//        }
//    }
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> subList = new ArrayList<>();
        dfs(res, subList, candidates, target, 0);
        return res;
    }
    private void dfs(List<List<Integer>> res, List<Integer> subList, int[] candidates, int target, int index) {
        if (index==candidates.length) return;
        if (target==0){
            res.add(new ArrayList<>(subList));
            return;
        }
        dfs(res, subList, candidates, target, index+1);
        if (target-candidates[index]>=0){
            subList.add(candidates[index]);
            dfs(res, subList, candidates, target-candidates[index], index);
            subList.remove(subList.size()-1);
        }
    }
}